package _10_Recursion;

/**
 * 定义 : 在方法体内部调用当前方法 就是自己调用自己
 * 
 * 基本思想 : 以此类推是基本思想 循环也是,递归和迭代是等价的(迭代就是循环) 步长、终止条件、初始值
 * 
 * 应用场景 : 一般树状结构的都可以使用递归查询
 * 
 * 递归比普通的算法耗内存,运行效率比较低,谨慎使用,能用循环,尽量不用递归
 * 
 * 常见问题 : 需要删除一个目录下所有的文件以及子文件,类似的树状结构需求, 斐波那契数列这种有规律的也可以,累加加和、阶乘、汉诺塔等
 * 
 * 难点 : 不容易理解,可以画栈帧调用链
 * 
 * @author lenovo
 * @Date 2020年6月29日
 * @Time 下午5:56:02
 */
public class Recursion_01 {

	public static void main(String[] args) {
		System.out.println(sum(100));
		// 5050
		System.out.println(m1(5));
		// 15
		m2(5);
		// m1();
	}

	// 因为没有终止条件,所以栈内存溢出
	// Exception in thread "main" java.lang.Error: Unresolved compilation problem:
	public static void m1() {
		m1();
	}

	public static int sum(int a) {
		// 使用for完成1-100的累加加和
		int sum = 0;
		for (int i = 1; i <= a; i++) {
			sum += i;
		}
		return sum;
	}

	public static int m1(int a) {
		if (a == 1) {
			return 1;
		} else {
			// 5 = 5 + 4 + 3 + 2 + 1
			// 5 + m1(4)
			// 4 + m1(3)
			// 3 + m1(2)
			// 2 + m1(1)
			// 1
			return a + m1(--a);
		}
	}

	static int sum = 0;

	public static void m2(int a) {
		if (a == 1) {
			sum += 1;
			System.out.println(sum);
			return;
		}
		sum += a;
		m2(a - 1);
		// sum=sum+5+4+3+2+1=15
		// sum=sum+5,m2(4)
		// sum=sum+4,m2(3)
		// sum=sum+3,m2(2)
		// sum=sum+2,m2(1)
		// sum=sum+1
	}
}
